Large scale data centers typically comprise organized clusters of hardware running collections of standard software packages, such as web servers, database servers, and the like. Distributed computing services may be provided using devices on a network comprising multiple interconnected data centers. Database replication services allow a service provider to maintain one or more backup copies of their data at multiple locations on the network. Existing data backup solutions enable a user to store backup information in a location and/or on media that are separate from an original source. Data from one machine may be backed-up or replicated to separate databases at remote network locations. This replicated data can be retrieved to restore a database or service in the event of a failed machine.
In a cloud computing environment, for example, a service may use a predetermined number of replicas for all databases, such as a primary replica and one or more secondary replicas. Each database replica is maintained on a separate machine, which is often located remote from machines hosting other replicas of the same data. When a machine fails and does not come back online for a considerable amount of time, such as two hours, the replica stored on the failed machine will be lost and must be rebuilt. The larger the amount of data that is lost, the more time it will take to rebuild the lost replica. During the time it takes to rebuild the lost replica, there are only two replicas available. This further increases the risk of data loss if the primary replica or a secondary replica fails while the lost replica is being replaced.